//
// Created by Lenovo on 2020/10/23.
//

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod =  1e4;
#define ll long long
struct node
{
    ll a[15][15];
}x,y;
node mul(node x,node y)
{
    node tmp;
    for(int i = 0;i<2;i++)
    {
        for(int j = 0;j<2;j++)
        {
            tmp.a[i][j] = 0;
            for(int k = 0;k<2;k++)
            {
                tmp.a[i][j] =(tmp.a[i][j]+(x.a[i][k]*y.a[k][j])%mod)%mod;
            }
        }
    }
    return tmp;
}
void init()
{
    x.a[0][0] = 1;
    x.a[0][1] = 0;
    x.a[1][0] = 0;
    x.a[1][1] = 1;
    y.a[0][0] = 1;
    y.a[0][1] = 1;
    y.a[1][0] = 1;
    y.a[1][1] = 0;
}
ll qpow(ll n)
{
    init();
    while(n)
    {
        if(n&1)  x = mul(x,y);
        y = mul(y,y);
        n = n>>1;
    }
    /*for(int i = 0;i<2;i++)
    {
        for(int j = 0;j<2;j++)
        {
            printf("%lld ",x.a[i][j]);
        }
        printf("\n");
    }*/

    ll ans = x.a[0][0];
    return ans;
}
int main()
{
    ll n;
    while(scanf("%lld",&n)&&n!=-1)
    {
        if(n==0) cout<<0<<endl;
        else if(n==1) cout<<"1"<<endl;
        else
        {
            ll ans = qpow(n-1);
            cout<<ans<<endl;
        }
    }
}